首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 。
进一步可以发现这是一个充要条件。因为大于 的数一定能填补到小于 的数。
记一个合法的区间为 , 为 的前缀和。
记
则有
我们可以处理出 ,然后就可以用单调栈求解了。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1000000;
int n , m , k , a[ MAXN + 5 ] , Top , Stk[ MAXN + 5 ];
long long sum[ MAXN + 5 ];
int main( ) {
// freopen("blocks.in","r",stdin);
// freopen("blocks.out","w",stdout);
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&a[ i ]);
while( m -- ) {
scanf("%d",&k);
for( int i = 1 ; i <= n ; i ++ )
sum[ i ] = sum[ i - 1 ] + a[ i ] - k;
int Ans = 0;
Top = 0; Stk[ ++ Top ] = 0;
for( int i = 1 ; i <= n ; i ++ )
if( sum[ i ] < sum[ Stk[ Top ] ] ) Stk[ ++ Top ] = i;
for( int i = n ; i >= 1 ; i -- ) {
while( Top && sum[ i ] - sum[ Stk[ Top ] ] >= 0 ) Top --;
Ans = max( Ans , i - Stk[ Top + 1 ] );
}
printf("%d ",Ans);
}
return 0;
}